|
In computer science, an LL parser is a top-down parser for a subset of context-free languages. It parses the input from Left to right, performing Leftmost derivation of the sentence. An LL parser is called an LL(''k'') parser if it uses ''k'' tokens of lookahead when parsing a sentence. If such a parser exists for a certain grammar and it can parse sentences of this grammar without backtracking then it is called an LL(''k'') grammar. LL(''k'') grammars can generate more languages the higher the number ''k'' of lookahead tokens. A corollary of this is that not all context-free languages can be recognized by an LL(k) parser. An LL parser is called an LL('' *'') parser (an LL-regular parser) if it is not restricted to a finite ''k'' tokens of lookahead, but can make parsing decisions by recognizing whether the following tokens belong to a regular language (for example by means of a Deterministic Finite Automaton). LL grammars, particularly LL(1) grammars, are of great practical interest, as parsers for these grammars are easy to construct, and many computer languages are designed to be LL(1) for this reason. LL parsers are table-based parsers, similar to LR parsers. LL grammars can also be parsed by recursive descent parsers. == Overview == For a given context-free grammar, the parser attempts to find the leftmost derivation. Given an example grammar : 1. 2. 3. the leftmost derivation for is: Generally, there are multiple possibilities when selecting a rule to expand given (leftmost) non-terminal. In the previous example of the leftmost derivation, in step 2: We can choose from two rules: 2. 3. To be effective, the parser must be able to make this choice deterministically when possible, without backtracking. For some grammars, it can do this by peeking on the unread input (without reading). In our example, if the parser knows, that the next unread symbol is the only correct rule that can be used is 2. Generally, parser can look ahead at symbols. However, given a grammar, the problem of determining if there exists a parser for some that recognizes it, is undecidable. For each , there is a language that cannot be recognized by parser, but can be by . We can use the above analysis to give the following formal definition: Let be a context-free grammar and . We say that is , if and only if for any two leftmost derivations: 1. 2. Following condition holds: Prefix of the string of length equals the prefix of the of length implies . In this definition, is the starting and any non-terminal. The already derived input , and yet unread and are strings of terminals. The greek letters , and represent any string of both terminals and non-terminals (possibly empty). The prefix length corresponds to the lookahead buffer size, and the definition says that this buffer is enough to distinguish between any two derivations of different words. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「LL parser」の詳細全文を読む スポンサード リンク
|